Electronic devices such as smart phones, portable navigation devices (PNDs) and integrated navigation systems that include GNSS (global navigation satellite systems), such as GPS, signal reception and processing functionality are widely employed as personal, in-car or other vehicle navigation systems. In general terms, a known electronic device having navigation functionality comprises a processor, memory (at least one of volatile and non-volatile, and commonly both), and digital map data stored within said memory. The processor and memory cooperate to provide an execution environment in which a software operating system may be established, and additionally it is commonplace for one or more additional software programs to be provided to enable the functionality of the PND to be controlled, and to provide various other functions.
Typically these devices further comprise one or more input interfaces that allow a user to interact with and control the device, and one or more output interfaces by means of which information may be relayed to the user. Illustrative examples of output interfaces include a visual display and a speaker for audible output. Illustrative examples of input interfaces include one or more physical buttons to control on/off operation or other features of the device (which buttons need not necessarily be on the device itself but could be on a steering wheel if the device is built into a vehicle), and a microphone for detecting user speech. In a particularly preferred arrangement the output interface display may be configured as a touch sensitive display (by means of a touch sensitive overlay or otherwise) to additionally provide an input interface by means of which a user can operate the device by touch.
Devices of this type will also often include one or more physical connector interfaces by means of which power and optionally data signals can be transmitted to and received from the device, and optionally one or more wireless transmitters/receivers to allow communication over cellular telecommunications and other signal and data networks, for example Wi-Fi, Wi-Max, GSM, and the like.
PND devices of this type also include a GPS antenna by means of which satellite-broadcast signals, including location data, can be received and subsequently processed to determine a current location of the device.
The PND device may also include electronic gyroscopes and accelerometers which produce signals that can be processed to determine the current angular and linear acceleration, and in turn, and in conjunction with location information derived from the GPS signal, velocity and relative displacement of the device and thus the vehicle in which it is mounted. Typically such features are most commonly provided in in-vehicle navigation systems, but may also be provided in PND devices if it is expedient to do so.
The utility of such PNDs is manifested primarily in their ability to determine a route between a first location (typically a start or current location) and a second location (typically a destination). In known devices, these locations can be input by a user of the device, by any of a wide variety of different methods, for example by postcode, street name and house number, name, etc. In some known navigation devices, navigable destinations are stored locally in a data repository as library of data records representative of locations relevant to a digital map. For locations that represent navigable destinations, location information, such as latitude and longitude or a distance along a path between nodes in the digital map, may be stored to allow the destination to be located, and a navigable route to that location to be generated.
Typically, location data records for navigable destinations may represent addresses having components (or data fields) including house number, street name, settlement name, country and postal code that together define a specific address. Location data records for destinations may also represent previously stored manufacturer-supplied or user-generated points of interest (POIs), which may be “well known” destinations (such as famous locations, municipal locations (such as sports grounds or swimming baths) or other points of interest such as restaurants, bars, shops, etc. POI data records may have components including one or more of the POI name (e.g. “British Museum”), POI brand name (e.g. “Starbucks”), POI category name and/or category code (e.g. “restaurant” and “7315”) and POI address (including house number, street name, settlement name, postal code and country). Data records may also be stored for favourite or recently visited destinations.
Typically, the PND is enabled by software for computing a “best” or “optimum” route between the start and destination address locations from the map data. A “best” or “optimum” route is determined on the basis of predetermined criteria and need not necessarily be the fastest or shortest route. The selection of the route along which to guide the driver can be very sophisticated, and the selected route may take into account existing, predicted and dynamically and/or wirelessly received traffic and road information, historical information about road speeds, and the drivers own preferences for the factors determining road choice (for example the driver may specify that the route should not include motorways or toll roads).
In addition, the device may continually monitor road and traffic conditions, and offer to or choose to change the route over which the remainder of the journey is to be made due to changed conditions. Real time traffic monitoring systems, based on various technologies (e.g. mobile phone data exchanges, fixed cameras, GPS fleet tracking) are being used to identify traffic delays and to feed the information into notification systems.
PNDs of this type may typically be mounted on the dashboard or windscreen of a vehicle, but may also be formed as part of an on-board computer of the vehicle radio or indeed as part of the control system of the vehicle itself. The navigation device may also be part of a hand-held system, such as a PDA (Portable Digital Assistant), a media player, a mobile phone, smart phone or the like, and in these cases, the normal functionality of the hand-held system is extended by means of the installation of software on the device to perform both route calculation and navigation along a calculated route.
It is possible for a mobile device to be in wireless communication with a fixed terminal. The data storage and processing required to determine a destination and route could be performed in the fixed terminal with the mobile device transmitting the user input information to the fixed terminal and receiving information for displaying to a user of the mobile device from the fixed terminal. However, such an implementation requires a wireless connection to the mobile device, as well a minimum bandwidth for the information transfer, and neither of these can be ensured in all locations.
Accordingly, when a navigation device is a mobile device, the mobile device is required to store a large database of geographical information and to perform the searching of the database using the limited processing resources of the mobile device. In known navigation devices, a destination, such as an address or a POI, is searched for within a database of geographical information, in this case a data repository of data records representing locations relevant to a digital map, using a guided search.
A guided search uses prompts to request specific types of information from a user. The user's responses to each prompt allow a reduced search space to be defined for subsequent searches until a search result corresponding to the desired destination of a user is reached. Since each search space is smaller than the entire database of geographical information, the mobile device does not experience the problem of having to search the entire database of geographical information with its limited processing capability.
FIG. 5 shows an example of known a guided search process 500. The process begins at decision point 501 where the device prompts a user to input a selection of whether to search for an address or a point of interest (POI). If the user selects to search for an address, the user then receives three further prompts to input the name of a city 502, a street 503 within the city and a house number 504. If the user instead selects to search for a POI, the user is prompted to input the name of a city 505 and then to input a selection 506 of whether to search for a POI category 507 or POI name 508. The user then receives further prompts to input the POI category and/or POI name depending on the user selection. These searches iteratively narrow the search space by searching against specific components of the data records in relation to which the user is prompted for input, and filtering out those that do not have a component value that matches the user input.
Problems experienced by guided searches are that the plurality of prompts result in the device being slow and difficult to use. It is not sufficient for a user to provide information defining a desired destination with a single input to the device. In addition, a user may be unable to find a desired destination due to having incomplete information, or having information that does not tally exactly with the desired data record. Thus the user cannot easily speculatively search the database of geographical information to find a desired destination.
An alternative to performing a guided search is to perform a free text search. A free text search aims to determine the desired destination of a user from a single user input, thereby avoiding the plurality of prompts required to perform a guided search.
On such example of a free text searching technique for a navigation device is disclosed in WO 2010/119137 A1. The search is based upon a trie that associates names of geographical objects to collections of map tiles. A digital map is quadtree partitioned on a plurality of hierarchical levels. In order to reduce a search space so that a large database can be efficiently searched with the limited processing resources of the mobile device, a first search is performed at a level within the trie. If the number of candidate tiles exceeds a predetermined number, the search space is reduced by compacting some or all of the tiles in the candidate set to a next level tile. Accordingly, mobile device is not required to directly search spaces larger than a predetermined size.
However, a problem with the above-described free text search technique is that the mobile device is required to perform the processing required to reduce the search space after candidate results have been obtained. This processing to change the search space increases the processing requirements and slows down the retrieval of search results.
It is known in the art of PNDs to, besides a list view of search results, also provide a map view in which graphical user interface (GUI) elements are used to indicate locations of the results of a destination search, or weather events or traffic incidents. This can facilitate a user in contextually visualising the locations in relation to a digital map. However, showing these locations in a manner that is particularly usable and easily understandable to the user is problematic, as there can be too much or too little location information displayed, with too much or too little functionality, which may diminish the user experience and limit the ease of use of the device for selecting a destination to route to, or to effectively take into account relevant weather and traffic events.